use crate::list::list2::*;

pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    let mut curr = head;

    while let Some(mut curr_node) = curr.take() {
        let next_temp = curr_node.next.take();
        curr_node.next = prev.take();
        prev = Some(curr_node);
        curr = next_temp;
    }

    prev
}

/// a -> b -> c -> d
pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut fast_p = &head;
    let mut slow_p = &head;

    while fast_p.is_some() && fast_p.as_ref().unwrap().next.is_some() {
        slow_p = &slow_p.as_ref().unwrap().next;
        //fast_p twice step than slow_p
        fast_p = &fast_p.as_ref().unwrap().next.as_ref().unwrap().next;
    }

    slow_p.clone()
}

pub fn merge_two_list(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    match (l1, l2) {
        (Some(m), None) => Some(m),
        (None, Some(n)) => Some(n),
        (Some(mut m), Some(mut n)) => {
            if m.val < n.val {
                let a = m.next.take();
                m.next = merge_two_list(a, Some(n));
                Some(m)
            } else {
                let a = n.next.take();
                n.next = merge_two_list(Some(m), a);
                Some(n)
            }
        }
        _ => None,
    }
}